#include<assert.h>
#include<iostream>
#include<vector>
using namespace std;

template<class T>
struct My_less{
  bool operator()(T& l,T& r)
  {
    return l < r;
  }
};
template<class T>
struct My_greater{
  bool operator()(T& l,T& r)
  {
    return l > r;
  }
};
template<class T,class Container = vector<T>,class Compare = My_less<T>> //默认是大根堆
class priority_queue
{
public:
  priority_queue()
  {}
  ~priority_queue()
  {}
  void AdjustUp(int child) //向上调整
  {
    int parent = (child -1 )/2;
    while(parent >= 0)
    {
      if(_cmp(_con[parent],_con[child]))
      {
        ::swap(_con[parent],_con[child]);
        child = parent;
        parent = (child - 1) / 2;
      }
      else 
        break;
    }
  }
  void AdjustDown(int parent) //向下调整
  {
    int child = parent*2+1;
    int n = size();
    while(child < n)
    {
      if(child + 1 < n && _cmp(_con[child],_con[child+1]))
        child += 1;
      if(_cmp(_con[parent],_con[child]))
      {
        ::swap(_con[parent],_con[child]); 
        parent = child;
        child = parent * 2 + 1;
      }
      else 
        break;
    }
  }
  void push(const T& val)
  {
    _con.push_back(val);
    AdjustUp(_con.size()-1); 
  }
  void pop()
  {
    ::swap(_con[0],_con.back());
    _con.pop_back();
    AdjustDown(0);
  }
  bool empty() const 
  {
    return _con.empty();
  }
  T& top()
  {
    assert(!empty());
    return _con[0];
  }
  int size() const 
  {
    return _con.size();
  }
private:
  Container _con;
  Compare _cmp;
};
int main()
{
  //priority_queue<int,vector<int>,My_greater<int>> q; 
  priority_queue<int> q;
  q.push(1);
  q.push(2);
  q.push(3);
  while(!q.empty())
  {
    cout << q.top() <<" ";
    q.pop();
  }
  cout << endl;
  return 0;
}
